//
//  LinkList_8.swift
//  ArithmeticClass7
//
//  Created by xiangzuhua on 2020/9/30.
//  Copyright © 2020 xiang. All rights reserved.
//

import Foundation

// 基于数组的顺序栈
public class ArrayStack: NSObject {
    var items: Array<String>
    var count: Int
    var n: Int
    
    // 初始化
    public init(_ capacity: Int) {
        self.n = capacity
        self.count = 0
        self.items = [String](repeating: String(), count: capacity)
    }
    
    // 入栈操作
    func push(item: String) -> Bool {
        if count == n {// 数组空间不够了，直接返回false，入栈失败
            return false
        }
        items[count] = item
        count += 1
        return true
    }
    
    // 出栈操作
    func pop() -> String {
        if count == 0 {// 栈为空直接返回nil
            return String()
        }
        count -= 1
        let item = items[count]
        return item
    }
}

// 支持动态扩容的顺序栈
class ArrayMutabelStack: NSObject{
    var items: [String]
    var count: Int
    var n: Int
    
    public init(_ capacity: Int) {
        self.n = capacity
        self.count = 0
        self.items = [String](repeating: String(), count: capacity)
    }
    
    // 入栈操作
    public func push(item: String) -> Bool{
        if self.count == self.n {// 超过最大存储值，申请更大空间
            var tempArr = [String](repeating: String(), count: 2 * self.n)
            self.n *= 2
            for (index, ite) in self.items.enumerated() {
                tempArr[index] = ite
            }
            self.items.removeAll()
            self.items = tempArr
        }
        self.items[self.count] = item
        self.count += 1
        return true
    }
    
    // 出栈操作
    public func pop() -> String{
        if self.count == 0 {
            return String()
        }
        self.count -= 1
        let item = self.items[self.count]
        return item
    }
}

// 基于链表的链式栈
class LinkStack: NSObject {
    var head: ListNode?
    var n: Int
    var count: Int
    var next: ListNode?
    public init(_ capacity: Int) {
        self.n = capacity
        self.count = 0
        self.head = ListNode(0).next
        self.next = self.head
    }
    
    // 入栈
    public func push(_ node: ListNode) -> Bool {
        if self.count == 0 {
            self.head = node
            self.next = node
            self.count += 1
            return true
        }
        
        if self.count == n {
            return false
        }
        
        self.next?.next = node
        self.next = node
        self.count += 1
        return true
        
    }
    // 出栈
    public func pop() -> ListNode? {
        if self.count == 0 {
            return nil
        }
        
        var temp = ListNode(0).next
        if self.count == 1 {
            temp = self.next
            self.next = ListNode(0).next
            self.head = self.next
            return temp
        }
        
        var resultNode: ListNode? = self.head
        for _ in 0..<self.count {
            if resultNode?.next == self.next {
                temp = self.next
                self.next = resultNode
            }
            resultNode = resultNode?.next
        }
        self.count -= 1
        return temp
    }
}






















